Baum–Welch algorithm

In electrical engineering, computer science, statistical computing and bioinformatics, the Baum–Welch algorithm is used to find the unknown parameters of a hidden Markov model (HMM). It makes use of the forward-backward algorithm and is named for Leonard E. Baum and Lloyd R. Welch.

Contents

Explanation

The Baum–Welch algorithm is a particular case of a generalized expectation-maximization (GEM) algorithm. It can compute maximum likelihood estimates and posterior mode estimates for the parameters (transition and emission probabilities) of an HMM, when given only emissions as training data.

For a given cell  S_i in the transition matrix, all paths to that cell are summed. There is a link (transition from that cell to a cell  S_j ). The joint probability of  S_i , the link, and  S_j can be calculated and normalized by the probability of the entire string. Call this  \chi .

Now, calculate the probability of all paths with all links emanating from  S_i . Normalize this by the probability of the entire string. Call this  \sigma .

Now divide  \chi by  \sigma . This is dividing the expected transition from  S_i to  S_j by the expected transitions from  S_i . As the corpus grows, and particular transitions are reinforced, they will increase in value, reaching a local maximum. No way to ascertain a global maximum is known.

See also

References

The algorithm was introduced in the paper:

The Shannon Lecture by Welch, which speaks to how the algorithm can be implemented efficiently:

The path-counting algorithm, an alternative to the Baum–Welch algorithm:

External links